package com.sam.sort;

import java.util.TreeMap;

/**
 * 最长不重复子串
 * Created by samwang on 2017/11/13.
 */
public class MaxUnique {

    public static void main(String[] args) {
        String str1 = "hellowdhelloko";
//        String str1 = "a";
        longestSubstring(str1,str1.length());
    }

    //O(N^2)的时间复杂度
    static void max_unique(String str) {
        // begin用来保存 最长不重复子串的 开始索引
        int begin = 0;
        // maxlen用来保存最长不重复子串的 长度
        int maxlen = 0;
        // 定义一个容器，用来保存遍历时候遇到的每一个字符的出现次数情况
        TreeMap<Character, Integer> tm = new TreeMap<Character, Integer>();
        int n = str.length();

        int j = 0;
        for (int i = 0; i < n; ++i) {
            // 初始化   hash 这个数组，用0补充
            for (int k = 0; k < n; k++) {
                tm.put(str.charAt(k), 0);
            }
            tm.put(str.charAt(i), 1);
            // 往i+1开始往后找，遇到和i索引处不一样的元素，就将那个位置的“键值”置1；
            // 遇到一样的就 break，让j停在现在这个位置
            for (j = i + 1; j < n; ++j) {
                if (tm.get(str.charAt(j)) == 0)
                    tm.put(str.charAt(j), 1);
                else
                    break;
            }
            // 上面j刚好停在了，第一次出现重复的那个位置，相减即为这个时候的最长子串长度，
            // i索引是其的开始
            if (j - i > maxlen) {
                maxlen = j - i;
                begin = i;
            }
        }
        System.out.println(maxlen + " " + str.substring(begin, begin + maxlen));

    }



    //O(N)
     static int longestSubstring(String str, int n) {
        if (str == null || n == 0) {return 0; }
        char[] chas = str.toCharArray();
        int[] map = new int[256];
        for (int i = 0; i < 256; i++) { map[i] = -1;  }// 初始化
        int len = 0;  int pre = -1;
        int cur ;

        int begin = 0;
        for (int i = 0; i < n; i++) {
            pre = Math.max(pre, map[chas[i]]);//map[chas[i]] i前一个重复的位置, pre 上一个有重复的位置
            cur = i - pre;//当前的位置减去前一个重复的位置得到当前的长度, 得到两个相同字符间的长度+1，或者当前长度
            if (cur > len) {
                len = cur; //最长与当前的长度比较
                begin = pre + 1;
            }
            map[chas[i]] = i;
        }
        System.out.println(len + " " + str.substring(begin, begin + len));
        return len;//"hellowdhelloko"
    }
}